In the last decade, network coding has attracted a lot of interest. The advantages of network coding include improved throughput, robustness, scalability, and security. The performance gains are achieved by combining algebraically the packets at sources and/or at intermediate nodes in the network.
Network coding was first introduced in the seminal paper by R. Ahlswede, N. Cai, S. Y. R. Li, and R. W. Yeung, Network information flow, IEEE Transactions on Information Theory, 46(4):1204-1216, 2000. Both linear network coding, LNC, and random linear network coding, RLNC, achieve capacity when the field size is sufficiently large. However, performing operations in large finite fields is costly and complex.
RLNC can be several orders of magnitude more energy demanding and up to one order of magnitude slower than the encoding done by simple XOR operations. This has been reported in, for example, H. Shojania and B. Li, Random network coding on the iphone: fact or fiction?, NOSSDAV, 2009; M. V. Pedersen, F. H. P. Fitzek, and T. Larsen, Implementation and performance evaluation of network coding for cooperative mobile devices, In Proc. IEEE Cognitive and Cooperative Wireless Networks Workshop, 2008; and P. Vingelmann, M. V. Pedersen, F. H. P. Fitzek, and J. Heide, Multimedia distribution using network coding on the iphone platform, Proceedings of the 2010 ACM multimedia workshop on Mobile cloud media computing, 2010.
Some of the limitations of RLNC may therefore be overcome by implementing network coding only by XOR operations.
In S. Riis, Linear versus nonlinear boolean functions in network flow, CISS, 2004; it was shown that every solvable multicast network has a linear solution over GF(2). Wireless network coding by sending XORs was presented in S. Katti, H. Rahul, W. Hu, D. Katabi, M. Médard, and J. Crowcroft, XORs in the air: Practical wireless network coding, IEEE/ACM Trans. Netw, 16(3):497-510, 2008; where the main rule is that a node can XOR n packets together only if the next hop has all n−1 packets. The authors in J. Qureshi, Foh Chuan Heng, and Cai Jianfei, Optimal solution for the index coding problem using network coding over gf(2), In Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON), pages 209-217, 2012; address the index coding problem by proposing network coding over GF(2). The encoding scheme is based on bitwise XORing by adding redundant bits, and the decoding scheme is based on a simple bit after bit sequential back substitution method.
Usually randomized strategies are used for generating network codes, and not many structured strategies are known. The known structured approaches to network coding are mostly based on combinatorial design theory. Combinatorial design theory is an area of combinatorial mathematics with many communications applications. Sending linear combinations of packets instead of uncoded data offers security against eavesdropping attacks. In N. Cai and R. W. Yeung, Secure network coding, In IEEE International Symposium on Information Theory, page 323, 2002; the authors incorporate network coding and information security based on Shamir's secret sharing algorithm. The authors in K. Harada and H. Yamamoto, Strongly secure linear network coding, IEICE Transactions, 91-A(10):2720-2728, 2008; present an algorithm on how to construct a strongly k-secure network code and how to transform a nonsecure linear network code to a strongly k-secure network code if the alphabet size is sufficiently large. Although there are codes that can empower security in coded networks, the big alphabet size of these coding approaches is not desirable.
Accordingly, a number of problems are experienced by known approaches to network coding.